Вам нужно реализовать двоичное дерево поиска, поддерживающее четыре основные операции.
- Количество операций — $N$, где $1 \le N \le 2 \cdot 10^5$.
- вст к: Вставить целочисленный ключ $k$ в ДДП. Если ключ $k$ уже существует, данная операция ничего не делает.
- найти к: Найти ключ $k$. Вывести 'true', если он существует, иначе 'false'.
- след к: Найти преемника ключа $k$ — наименьший ключ в дереве, строго больший $k$. Вывести 'null', если такого ключа нет.
- пред к: Найти предшественника ключа $k$ — наибольший ключ в дереве, строго меньший $k$. Вывести 'null', если такого ключа нет.
- Ключевое предположение: Для запросов преемника и предшественника ключ $k$ гарантированно присутствует в дереве.